import java.util.HashMap;
import java.util.Map;

/**
 * 1419. 数青蛙
 * https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/
 */

class Solution {
    public int minNumberOfFrogs1(String croakOfFrogs) {
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('c', 0);
        map.put('r', 0);
        map.put('o', 0);
        map.put('a', 0);
        map.put('k', 0);
        if(croakOfFrogs.charAt(0) != 'c') return -1;
        int len = croakOfFrogs.length();
        for(int i = 0; i < len; i++) {
            char ch = croakOfFrogs.charAt(i);
            if(ch == 'c') {
                if(map.get('k') == 0) map.put('c', map.get('c') + 1);
                else {
                    //hash里的k >= 1 
                    map.put('c', map.get('c') + 1);
                    map.put('k', map.get('k') - 1);
                }
                if(map.get('k') < 0) return -1;
            } else if(ch == 'r') {
                map.put('c', map.get('c') - 1);
                map.put('r', map.get('r') + 1);
                if(map.get('c') < 0) return -1;
            } else if(ch == 'o') {
                map.put('r', map.get('r') - 1);
                map.put('o', map.get('o') + 1);
                if(map.get('r') < 0) return -1;
            } else if(ch == 'a') {
                map.put('o', map.get('o') - 1);
                map.put('a', map.get('a') + 1);
                if(map.get('o') < 0) return -1;
            } else {
                //ch == 'k'
                map.put('a', map.get('a') - 1);
                map.put('k', map.get('k') + 1);
                if(map.get('a') < 0) return -1;
            }
        }
        if((map.get('c') != 0 || map.get('r') != 0 || map.get('o') != 0 ||
            map.get('a') != 0) && map.get('k') == 0) return -1;
        if(map.get('c') > 0 && (map.get('r') == 0 || map.get('o') == 0 ||
            map.get('a') == 0 || map.get('k') == 0)) return -1;
        return map.get('k');
    }

    //优化
    public int minNumberOfFrogs(String c) {
        char[] croakOfFrogs = c.toCharArray();
        String s = "croak";
        int n = s.length();
        int[] hash = new int[n];//数组模拟hash

        Map<Character, Integer> map = new HashMap<>();//x对应x这个字符的下标
        for(int i = 0; i < n; i++) {
            map.put(s.charAt(i), i);
        }

        for(char ch : croakOfFrogs) {
            int i = map.get(ch);
            //ch == 'c'
            if(i == 0) {
                if(hash[n - 1] != 0) hash[n - 1]--;
                hash[i]++;
            } else {
                //ch != 'c'
                if(hash[i - 1] == 0) return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }

        for(int i = 0; i < n - 1; i++) {
            if(hash[i] != 0) return -1;
        }

        return hash[n - 1];
    }
}